package leetcode.primary;

import java.util.HashMap;
import java.util.Map;

public class T76 {
    public String minWindow(String s, String t) {
        int lens = s.length();
        int lent = t.length();
        if (lens<lent){
            return "";
        }
        StringBuilder ans = new StringBuilder();
        Map<Character,Integer> map = new HashMap<>();
        //将字符串t存到hashmap中
        for (int i = 0; i < lent; i++) {
            Integer value = map.getOrDefault(t.charAt(i), 0);
            map.put(t.charAt(i),value+1);
        }

        //len表示子串中还未匹配到的字符数
        int len=lent;
        int start=0,end=0;
        for (int i = 0; i < lens; i++) {
            Integer integer = map.get(s.charAt(i));

            //若存在则让value--
           if (integer!=null){
               map.replace(s.charAt(i),--integer);
               //integer<0是因为对应的字符在子串中出现的次数大于t中出现的次数
               //只要考虑integer>=0的情况
               if (integer>=0){
                   len--;
               }
           }
           end++;
           if (len==0){
               while ( start<end){
                   Integer temp = map.get(s.charAt(start));
                   //左指针往里缩
                   if(temp==null){
                       start++;
                       continue;
                   }
                   if(temp<0){
                       map.replace(s.charAt(start),++temp);
                   }else {
                       break;
                   }
                   start++;
               }
               if ( ans.length()>0 && ans.length()>s.substring(start,end).length()){
                       ans.delete(0,ans.length());
                       ans.append(s,start,end);
               }
               //这里很重要，len==0,符合条件子串出现;start++,说明start对应的字符缺少了,所以len=1，将对应的映射值+1或者直接赋值为1
               len = 1;
               map.replace(s.charAt(start),1);
               start++;
           }
        }
        return ans.toString();
    }

    public static void main(String[] args) {
        T76 test = new T76();
        String s = test.minWindow("a", "a");
        System.out.println(s);
    }
}
